package com.qjc.demo.algorithm;

import java.util.Arrays;

/**
 * @ClassName: SingleNumber
 * @Description: xml-58同城面试过：给定一个无序数组, 打印出只出现一次的数字 ,要求不可开辟空间
 * 例如：{6, 5, 2, 7, 3, 5, 2, 6, 3};
 * 打印：7
 * @Author: qjc
 * @Date: 2022/5/1 11:52 PM
 */
public class SingleNumber {

    /**
     * 解题思路1：
     * 任何数与0异或，结果仍然是原来的数；
     * 任何数与其自身做异或运算，结果都是0；
     * 异或运算满足减缓率和结合律，即a^b^a=b^a^a=b^(a^a)=b^0=b
     */
    public static int solution1(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single = single ^ num;
        }
        return single;
    }

    public static int solution2(int[] nums) {
        Arrays.sort(nums);
        int index = 0;
        while (index < nums.length - 1) {
            if (nums[index] != nums[index + 1]) {
                break;
            }
            index = index + 2;
        }
        return nums[index];
    }

    public static void main(String[] args) {
        int[] nums = {6, 5, 2, 7, 3, 5, 2, 6, 3};
        System.out.println(solution1(nums));
        System.out.println(solution2(nums));
    }

}
